﻿#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<map>
using namespace std;


//关于map 容器的使用
//主要关于其insert 函数的使用
int main01()
{
	map<string, string> dict;
	dict.insert({ "sort", "" });    //可以直接大括号插入
	
	dict["left"] = "";        //[ ] 运算符本质上也是insert 函数，而insert 函数会先查找是否存在该key 值，如果存在则更新，不存在的新插入

	dict["right"];      //不给val 的情况下，默认调用默认构造

	dict["right"] = "ұ";    //会更新right     //因为一定会调用key 为right ，并更改其对应的val

	cout << dict["left"] << endl;       

	dict.insert({ "sort", "xxxx" });    //不会更新sort
                                      //因为当你写 dict["sort"] = "xxxx"; 时，无论 "sort" 是否存在，都会返回对应 value 的引用，然后将其赋值为 "xxxx"。
                                      //这就实现了“插入或更新”的效果。而 insert 只在 key 不存在时插入，不会覆盖已有的值。
	return 0;                         //为此我们也可以通过insert 的返回值，来判断当前对象中是否存在该key 值。
}



//multimap
int main02()
{
	multimap<string, string> dict;
	dict.insert({ "sort", "" });
	dict.insert({ "sort", "" });        //由于是multimap 因此都能添加进去
	dict.insert({ "sort", "xxxx" });
	dict.insert({ "left", "" });

	dict.erase("sort");      //multimap 中的删除会将所有该key 都删除
	auto itpair = dict.equal_range("sort");    //equal_range(key) 返回一个 pair<iterator, iterator>，表示所有 key 等于指定值的元素的区间。
	auto it = itpair.first;                                                   // 起始       结束    左闭右开
	while (it != itpair.second)
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

	return 0;
}



///////////////////////////////////////////
//AVL树 (平衡二叉搜索树）

#include"AVLTree.h"

// 测试代码
void TestAVLTree1()
{
    AVLTree<int, int> t;
    // 常规的测试用例
    //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    // 特殊的带有双旋场景的测试用例
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a)
    {
        if (e == 14)       //进一步细查err原因
         {
             int x = 0;      //定义变量作为打断点的语句
         }
        t.Insert({ e, e });
        cout << "Insert" << e << "->";          //快速查错   每次都打印判断是否为平衡树来判断是否err
        cout << t.IsBalanceTree() << endl;
    }

    t.InOrder();
    cout << t.IsBalanceTree() << endl;
}

#include<vector>

// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));

    for (size_t i = 0; i < N; i++)
    {
        v.push_back(rand() + i);
    }

    size_t begin2 = clock();
    AVLTree<int, int> t;
    for (auto e : v)
    {
        t.Insert(make_pair(e, e));
    }
    size_t end2 = clock();

    cout << "Insert:" << end2 - begin2 << endl;
    cout << t.IsBalanceTree() << endl;

    cout << "Height:" << t.Height() << endl;
    cout << "Size:" << t.Size() << endl;

    size_t begin1 = clock();
    // 确定在的值
    /*for (auto e : v)
    {
            t.Find(e);
    }*/

    // 随机值
    /*for (size_t i = 0; i < N; i++)
    {
        t.Find((rand() + i));
    }*/

    size_t end1 = clock();

    cout << "Find:" << end1 - begin1 << endl;
}

int main()
{
    TestAVLTree1();
    //TestAVLTree2();

    return 0;
}